Pattern matching is a technique by which a test image is matched to a template or stored image. This process is typically referred to as template matching. Normalized cross-correlation (NCC) is the standard for template matching in images. Until recently, correlations have been used in novel template-matching devices, such as those described by TI Kaneko and O Hori in U.S. Pat. No. 7,085,418, titled, “Template matching method and image processing device.” NCC can find exact matches; however, its disadvantage is the computational complexity. In other words, NCC scales as the volume of the image times the volume of the template. Thus, for high-density integrated circuits (ICs), the search time can be prohibitive (e.g., greater than 1000 hours). Despite this limitation, NCC has been hardly improved upon: typical speed-ups are slightly (about 2×), as was described by L. Di Stefano and S. Mattoccia, in “A sufficient condition based on the Cauchy-Schwarz inequality for efficient Template Matching”, IEEE Int. Conf on Image Processing (ICIP 2003), Sep. 14-17, 2003.
To speed up cross-correlation, Fourier transformations (FT) have been used (see L. G. Brown, “A survey of image registration techniques,” ACM Comput Surv., vol. 24, no. 4, pp. 325-376, 1992). FT can greatly reduce the time to compute the correlation between test image and template. However, computing the FT on the test image requires N log2(N) operations, where N is the number of pixels. Thus, for large images, which are typical for ICs, this computation alone can be more expensive than the total computation required for our invention.
Another group of methods, iterative search methods (e.g., swarm vision as described by Owechko et al. in U.S. Pat. No. 7,599,894), do not search exhaustively in the test image; instead, they iteratively move the template location within the test image until a high correlation is achieved. These methods perform well if the test image is sufficiently blurry such that a gradient exists that points in the direction of higher correlation. However, for exact matching, as in circuit leaf-cell search, such methods are not optimal.
The present invention is also related to pattern recall in recurrent neural networks (RNN), such as those described by J. J. Hopfield in “Neural networks and physical systems with emergent collective computational abilities”, Proceedings of the National Academy of Sciences of the USA, vol. 79 no. 8 pp. 2554-2558, April 1982, which is incorporated herein by reference. As in the present invention, the neural networks first store template patterns. Different from the present invention, however, these patterns are stored by adjusting weights of neural connections instead of delays. In pattern recall from RNNs, a pattern is first fed into the input neurons, and then, the network's dynamics converge to a related stored pattern. This process is also called pattern association. A disadvantage of this process is the low speed. Computing the network dynamics is an iterative process. Moreover, such networks alone do not provide an efficient mechanism to feed the whole test image into the network. Therefore, as in cross-correlation, every test image location would need to be compared with the template image. As result, using RNNs for pattern matching would be slower than using normalized cross-correlation.
As evident above, the state of the art in image template matching is normalized cross-correlation, which has not been significantly improved upon for several decades. Thus, continuing need exits for a pattern matching system with a substantial speed improvement over existing and traditional systems.